package queue;

public class Myqueue {
    //Queue是一个接口，在实例化时必须实现 linkedList 的对象 ， 因为 linkedList 实现了 Queue 接口
    //建议使用链表来实现队列
    //单向链表 ， 如果没有 last 这个引用的时候 ， 不管那便是队头 ， 或者队尾 ， 都是不能同时让入队和出队达到 O(1) 的
    //如果有 last 这个引用 ， 建议从尾入从头出 ， 此时可以达到 O(1) 如果从头入 ， 从尾删 ， 是打达倒的
    //双向链表可以当作队列

    //一双向链表实现一个队列
    //思考这些方法 有什么区别

    //循环列表 哪种情况判断满 ， 哪种情况判断空
    //rear = (rear+1)%len 开始和满了 rear 和front 都在同一个节点
    //此时那种情况判断满了？ 定义一个size来记录存储的个数 size ==len 满了； size == 0 空
    //每次存储时判断下一个是不是 front ， 如果是那就不存储了

    //设计循环队列 力扣622

    //双端队列Deque

    //以双向链表实现队列
    static class Node {
        private int val;
        private Node prev;
        private Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node front;
    public Node rear;

    //相当于尾插(尾进)
    public void offer(int val) {
        Node node = new Node(val);
        if (front == null) {
            front = node;
            rear = node;
        } else {
            rear.next = node;
            node.prev = rear;
            rear = node;
        }
    }
    //删除节点（头出）
    public int poll() {
        if (front == null) {
            return -1;
        }
        int val = front.val;
        front = front.next;
        if (front != null) {
            front.prev = null;
        } else {
            rear = null;
        }
        return val;
    }

    public int size() {
        Node cur = front;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

    public int peek() {
        if (front == null) {
            return -1;
        }
        return front.val;
    }
}
